package imooc_math;

import java.util.Arrays;

public class InversionCount {
	static int count=0;
	public static int test(int[] arry){
		int num=0;
		for(int i=0;i<arry.length;i++){
			for(int j=i+1;j<arry.length;j++){
				if(arry[i]>arry[j]){
					num++;
				}
			}
		}
		return num;
	}
	
	public static int[] test1(int[] arry){
		int n=arry.length;
		sort(arry,0,n-1);
		return arry;
	}
	public static void sort(int[] arry,int l,int r){
		if(l>=r){
			return;
		}
		int mid=(l+r)/2;
		//[l,mid] [mid+1,r]
		sort(arry,l,mid);
		sort(arry,mid+1,r);
		merge(arry,l,mid,r);
	}
	public static void merge(int[] arry,int l,int mid,int r){
		//记录逆序对的个数
		int[] tmp=Arrays.copyOfRange(arry, l, r+1);
		System.out.println(Arrays.toString(tmp)+"  "+tmp.length);
		int i=l,j=mid+1;
		for(int k=l;k<=r;k++){//对每一个元素都进行比较
			if(i>mid){
				arry[k]=tmp[j-l];
				j++;
			}else if(j>r){
				arry[k]=tmp[i-l];
				i++;
				//count++;
				//System.out.println(k+" "+(j-l));
			}else if(tmp[i-l]<=tmp[j-l]){
				arry[k]=tmp[i-l];
				i++;
			}else{
				arry[k]=tmp[j-l];
				j++;
				count++;
				System.out.println(k+" "+(j-1-l)+" "+count);
				 // 此时, 因为右半部分k所指的元素小
                // 这个元素和左半部分的所有未处理的元素都构成了逆序数对
                // 左半部分此时未处理的元素个数为 mid - j + 1
               // res += (long)(mid - i + 1);
			}
		}
	}
	public static void main(String[] args) {
		int [] arry=new int[]{3,2,1};
		System.out.println(Arrays.toString(test1(arry)));
		System.out.println(count);
	}
}
